﻿//////////////////////////////////////////////////////////////////
//
// PriorityQueue.cs
//
// Copyright (c) 2012 Dan Pike.
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation files
// (the "Software"), to deal in the Software without restriction,
// including without limitation the rights to use, copy, modify, merge,
// publish, distribute, sublicense, and/or sell copies of the Software,
// and to permit persons to whom the Software is furnished to do so,
// subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included
// in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
// IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
// TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
// SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Wintellect.PowerCollections;

namespace Utilities
{
   public class PriorityQueue<T, V> : IComparer<T>
      where T : class
   {
      private ComparePriorityHandler comparer_;
      private Dictionary<T, V> priority_;
      private OrderedBag<T> bag_;
      public delegate int ComparePriorityHandler(V x, V y);

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      public PriorityQueue(ComparePriorityHandler comparer)
      {
         comparer_ = comparer;
         bag_ = new OrderedBag<T>(this);
         priority_ = new Dictionary<T, V>();
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// Set the priority for an object, adding it if we don't already have it
      /// </summary>
      /// <param name="entity"></param>
      /// <param name="priority"></param>
      public void SetPriority(T entity, V priority)
      {
         priority_[entity] = priority;
         bag_.Remove(entity);
         bag_.Add(entity);
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <returns></returns>
      public int Count
      {
         get { return bag_.Count; }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <returns></returns>
      public V PeekNextPriority()
      {
         return priority_[bag_[0]];
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      public T RemoveNext()
      {
         if (0 == bag_.Count)
         {
            return null;
         }
         T next = bag_.RemoveFirst();
         priority_.Remove(next);
         return next;
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// Implementation of IComparer<>
      /// </summary>
      /// <param name="x"></param>
      /// <param name="y"></param>
      /// <returns></returns>
      public int Compare(T x, T y)
      {
         try
         {
            V vX = priority_[x];
            V vY = priority_[y];
            int result = comparer_(vX, vY);
            if (0 == result)
            {
               // Same priority, so sort in object order
               result = x.GetHashCode() - y.GetHashCode();
            }
            return result;
         }
         catch (System.Exception ex)
         {
            new Logger().Exception(ex);
         }
         return 0;
      }
   }
}
